<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>Document</title>
    </head>
    <body>
        <script>
            /* 
              ①定义dp数组和下标含义：
               dp[i][j]表示长度为i，下标为(0,i-1)的字符串word1变化到长度为j的字符串word2所需要的最少操作数
              ②状态转移方程：
                字符串问题一般都是逐个比较尾序列
                if(word1[i-1]!=word2[j-1])，那么需要考虑三种情况：删除、替换、添加
                2.1删除 hors  hor  只需要删除s，继续考虑(0,i-2)和(0,j-1)的最少操作次数
                dp[i][j]=dp[i-1][j]+1
                2.2替换  hos  hor  只需要替换尾序列，操作+1，继续考虑(0,i-2)到(0,j-2)的最少操作次数
                dp[i][j]=dp[i-1][j-1]+1
                2.3添加 其实添加等同于删除word2的尾序列 
                dp[i][j]=dp[i][j-1]+1
                综上dp[i][j]=Math.min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1])+1

                如果相等 word1[i-1]==word2[j-1]
                dp[i][j]=dp[i-1][j-1]


              ③初始化dp数组
               当word1为空时，dp[0][j]=j
               word2为空 dp[i][0]=i
               ④确定遍历顺序
                当前状态依赖于前面状态，从左上往右下遍历            
            */
            var minDistance = function (word1, word2) {
                let dp = new Array(word1.length + 1).fill().map(() => new Array(word2.length + 1).fill(0))
                for (let i = 0; i <= word1.length; i++) {
                    dp[i][0] = i
                }
                for (let j = 0; j <= word2.length; j++) {
                    dp[0][j] = j
                }
                for (let i = 1; i <= word1.length; i++) {
                    for (let j = 1; j <= word2.length; j++) {
                        if (word1[i - 1] != word2[j - 1]) {
                            dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]) + 1
                        } else {
                            dp[i][j] = dp[i - 1][j - 1]
                        }
                    }
                }
                return dp[word1.length][word2.length]
            }
            minDistance("horse", "ros")
        </script>
    </body>
</html>
